This invention relates to a decoding apparatus and method for decoding data encoded in a linear cyclic code.
The Peterson method, Berlekamp-Massey method and Euclidean method are known generally as methods of obtaining an error position polynomial indicating a position of a symbol within a received word polynomial where an error occurs and an error evaluator polynomial indicating the value of the error of the symbol in decoding a linear cyclic code,
xe2x80x9cA Method for Solving Key Equation for Decoding Goppa Codes, Y. Sugiyama, M. Kasahara, S. Hirasawa and N. Namekawa, Inform. and Contr., Vol. 27, pp 87-99, January 1975xe2x80x9d (reference 1) discloses a Euclidean method.
xe2x80x9cAn erasures-Errors Decoding Algorithm for Goppa Codes (Y. Sugiyama, M. Kasahara and N. Namekawa, IEEE Trans., Inform. Theory, March 1976xe2x80x9d (reference 2) discloses that the Euclidean method can be applied to error erasure and correction processing by calculating an updated syndrome, i.e., by multiplying a syndrome polynomial with an erasure locator polynomial and erasing the (dxe2x88x921) th degree term where xe2x80x9cdxe2x80x9d is the minimum Hamming distance of the code (xe2x80x9cdxe2x80x9d is an odd number unless specifically mentioned).
The Euclidean method involves a computation load which is equal to or less than other methods. In addition, the Euclidean method is conveniently implemented in a hardware because computation is easily paralleled.
For example, Japanese PUPA 62-122332 discloses an apparatus in which the Euclidean method is implemented in a hardware. The apparatus disclosed in this reference (3) is so configured as to successively calculate an updated syndrome and a GCD (greatest common divisor) of two polynomials, and processes error erasure by using a systolic array technology.
In the apparatus disclosed in the reference 3, it is necessary for each calculating cell to be provided with a latch for holding information/status and multiplier/adder for calculation.
Japanese PUPA 7-202718 (reference 4), for example, discloses a decoding apparatus which comprises a less amount of hardware than the apparatus disclosed in the reference 2 by using a polynomial arithmetic processing circuit rather than a systolic array.
This invention provides a decoding apparatus and a method which allows data encoded in a linear cyclic code to be decoded with less hardware than the prior art decoding apparatus.
It is a further object of this invention to provide a decoding apparatus, an arithmetic apparatus and a method therefor which allows a linear cyclic code to be decoded in a speed equal to or higher than the prior art decoding apparatus with less hardware than the prior art decoding apparatus.
In order to achieve the above objectives, the decoding apparatus of this invention comprises erasure locator data calculating means for calculating erasure locator data xcex1i indicating the locator of erasure occurring in a linear cyclic code R(x), syndrome polynomial calculating means for calculating a syndrome polynomial S(x) based on said calculated erasure locator data xcex1i and said linear cyclic code R(x), updated syndrome polynomial calculating means for calculating an updated syndrome polynomial M(x) based on said erasure locator data xcex1i and said calculated syndrome polynomial S(x), polynomial calculating means for calculating an error position polynomial "sgr"(x) an erasure locator polynomial xcex(x) and an error evaluator polynomial xcfx89(x) based on said erasure locator data xcex1i and said calculated updated syndrome polynomial M(x), and decoding means for calculating an error/erasure value ei/Ei to correct the error/erasure in said linear cyclic code R(x) for decoding based on said calculated error position polynomial "sgr"(x) said calculated erasure locator polynomial xcex(x), said calculated error evaluator polynomial xcfx89(x), said error position data xcex1i, and said linear cyclic code R(x), said polynomial calculating means repeating recursive formulas;
"sgr"i(x)="sgr"ixe2x88x922(x)+Qi(x)xc2x7"sgr"ixe2x88x921(x)
xcfx89i(x)=xcfx89ixe2x88x922(x)+Qi(x)xc2x7xcfx89ixe2x88x921(x)
where Qi(x) is a quotient of xcfx89ixe2x88x922(x)/xcfx89ixe2x88x921(x), "sgr"xe2x88x92i(x)=1, xcfx89xe2x88x92i(x)=x2t, "sgr"o(x)=1, xcfx89o(x)=M(x),
until the degree of the polynomial xcfx89i becomes equal to or less than [(d+hxe2x88x921)/2xe2x88x921] (where [ ]is a Gauss symbol, d is a minimum Hamming distance and h is the number of erasures) to calculate the error position polynomial "sgr"(x) and the error evaluator polynomial xcfx89(x) for deriving the erasure locator polynomial xcex(x) from said erasure locator data xcex1i.
The decoding apparatus of this invention solves
S(x)xc2x7"sgr"(x)xc2x7xcex(x)=xcfx89(x) mod (x)xe2x80x83xe2x80x83(expression 12)
using the Euclidean method to derive the error evaluator polynomial xcfx89(x) and the error position polynomial "sgr"(x) for decoding a linear cyclic code such as BHC code. Rewriting the expression 12 by using the updated syndrome polynomial M(x)=S(x)xc2x7(x) mod xdxe2x88x921, xcfx86(x)xc2x7xdxe2x88x921xc2x1M(x)xc2x7"sgr"(x)=xcfx89(x) (expression 14) is obtained. The error position polynomial "sgr"(x) and the error evaluator polynomial xcfx89(x) can be uniquely obtained from this expression 14 except for the difference of a multiple of constant.
The polynomial calculating means of the decoding apparatus of this invention uses the expression;
xcexi(x)x2t+"sgr"i(x)xc2x7M(x)=xcfx89i(x)
(expression 16) Initial condition
xcexxe2x88x921(x)=1, "sgr"xe2x88x921(x)=0, xcfx89xe2x88x921(x)=X2t, xcex0(x)=1,
"sgr"0(x)=0, xcfx890(x)=M(x))
for solving the expression 14 using the Euclidean method.
The expression 16 can be expressed in the form of a recursive formula given below and the polynomial calculating means derives the error position polynomial "sgr"(x) and the error evaluator polynomial xcfx89(x) by repeating the following recursive formula until the condition deg xcfx89(x)xe2x89xa6[(d+hxe2x88x921)/2]xe2x88x921 is satisfied:
"sgr"i(x)="sgr"ixe2x88x922(x)+Qi(x)xc2x7"sgr"ixe2x88x921(x)
xe2x80x83xcfx89i(x)=xcfx89ixe2x88x922(x)+Qi(x)xc2x7xcfx891xe2x88x921(x)
where Qi(x) is quotient of xcfx89ixe2x88x922(x)/xcfx89ixe2x88x921(x),
The erasure locator polynomial xcex(x) is further calculated from the erasure locator data xcex1i as shown in the expression 8.
The decoding means obtains an error value ei and an erasure value Ei to correct a received word by substituting the expressions
ei=xcfx89(xcex1xe2x88x92ji)/{xcex1xe2x88x92jixc2x7xcex1xe2x80x2(xcex1xe2x88x92ji)xc2x7xcex(xcex1xe2x88x92ji)},xe2x80x83xe2x80x83(23)
Ei=xcfx89(xcex1xe2x88x92jxe2x80x2i)/{xcex1xe2x88x92jxe2x80x2ixc2x7xcex1xe2x80x2(xcex1xe2x88x92jxe2x80x2i)xc2x7xcex(xcex1xe2x88x92jxe2x80x2i)}xe2x80x83xe2x80x83(24)
with the erasure locator polynomial xcex(x), the error position polynomial "sgr"(x) and the error evaluator polynomial xcfx89(x) so obtained for correcting the received word to decode it.
The arithmetic apparatus of this invention calculates the error position polynomial "sgr"(x) and the error evaluator polynomial xcfx89(x) from the updated syndrome polynomial M(x) which is calculated from the erasure locator data xcex1i indicating the locator of an erasure in the linear cyclic code R(x) and the syndrome polynomial S(x) which is calculated from said erasure locator data xcex1i and said linear cyclic code R(x). Said arithmetic apparatus repeats recursive formulas;
"sgr"i(x)="sgr"ixe2x88x922(x)+Qi(x)xc2x7"sgr"ixe2x88x921(x)
xcfx89i(x)=xcfx89ixe2x88x922(x)+Qi(x)xc2x7xcfx89ixe2x88x921(x)
where Qi(x) is a quotient of xcfx891xe2x88x922(x)/xcfx89ixe2x88x921(x), "sgr"xe2x88x92i(x)=1, xcfx89xe2x88x92i(x)=x2t, "sgr"0(x)=1, xcfx890(x)=M(x),
until the degree of the polynomial xcfx89i becomes equal to or less than [(d+hxe2x88x921)/2xe2x88x921] (where [ ] is a Gauss symbol, d is a minimum Hamming distance and h is the number of erasures) to calculate the error position polynomial "sgr"(x) and the error evaluator polynomial xcfx89(x).
Preferably, said arithmetic apparatus comprises; two first registers (registers U, X) having a data width equal xe2x96xa1xe2x96xa1 to or greater than kxc2x7(dxe2x88x921)/2 bits (where k is the data length of a symbol included in said linear cyclic code), two second registers (registers Y, Z) having a data width equal to or greater than kxc2x7(dxe2x88x921)/2 bits (where k is the data length of a symbol included in said linear cyclic code), multiplier/divider means for multiplying/dividing two multiplication/division data items, a data selector for selecting two of polynomials held by said registers, said erasure locator data xcex1i and the result of said multiplication/division to generate said two multiplication/division data items, a first adder means for adding said result of multiplication/division to the data held in one of said first registers, a second adder means for adding said result of multiplication/division to the data held in one of said first registers, a shifter for shifting said result of multiplication/division, and arithmetic control means for causing these means to execute arithmetic processing to solve said recursive formula.
Preferably, said arithmetic control means causes one of said first registers (register U), the other one of said first registers (register X), one of said second registers (register Y), and the other one of said second registers (register Z) to hold said updated syndrome polynomial M(x), a coefficient xdxe2x88x921 of said linear cyclic code R(x), and values 0 and 1, respectively, and repeats an arithmetic operation for calculating said Q(x) and an exchange processing of the polynomial held in said register X to derive said error evaluator polynomial xcfx89(x) in said register X and said error position polynomial "sgr"(x) in said register Z.
The arithmetic operation to calculate said Q(x) calculates the highest degree term Q of the quotient of a division of the polynomial held in said register U by the polynomial held in said register X, and repeats a process of causing said register U to hold a polynomial derived by subtracting the result of a multiplication of the polynomial held in said register X with the calculated term Q from the polynomial held in said register X and a process of causing said register Y to hold a polynomial derived by subtracting the result of a multiplication of the polynomial held in said register Y with the calculated term Q from the polynomial held in said register X until the degree of the polynomial held in said register U becomes less than the degree of the polynomial held in said register X.
The exchange of the polynomials held in said registers causes the polynomial held in said register U to be exchanged with the polynomial held in said register X, and causes the polynomial held in said register Y to be exchanged with the polynomial held in said register Z.
Decoding Method
The decoding method of this invention comprises; an erasure locator data calculating step for calculating erasure locator data xcex1i indicating the locator of an erasure occurring in a linear cyclic code R(x), a syndrome polynomial calculating step for calculating a syndrome polynomial S(x) based on said calculated erasure locator data xcex1i and said linear cyclic code R(x), an updated syndrome polynomial calculating step for calculating an updated syndrome polynomial M(x) based on said erasure locator data a and said calculated syndrome polynomial S(x), a polynomial calculating step for calculating an error position polynomial "sgr"(x), an erasure locator polynomial xcex(x) and an error evaluator polynomial xcfx89(x) based on said erasure locator data xcex1i and said calculated updated syndrome polynomial M(x), and a decoding step for calculating error/erasure values ei/Ei based on said calculated error position polynomial "sgr"(x), said calculated erasure locator polynomial xcex(x), said calculated error evaluator polynomial xcfx89(x), said error position data xcex1i, and said linear cyclic code R(x) to correct an error/erasure in said linear cyclic code R(x) for decoding, said polynomial calculating step including;
a process of repeating a recursive formula:
"sgr"i(x)="sgr"ixe2x88x922(x)+Qi(x)xc2x7"sgr"ixe2x88x921(x)
xcfx89i(x)=xcfx89ixe2x88x922(x)+Qi(x)xc2x7xcfx89ixe2x88x921(x)
where Qi(x) is a quotient of xcfx89ixe2x88x922(x)/xcfx89ixe2x88x921(x), "sgr"xe2x88x92i(x)=1, xcfx89xe2x88x92i(x)=x2t, "sgr"0(x)=1, xcfx890(x)=M(x),
until the degree of the polynomial xcfx89i becomes equal to or less than [(d+hxe2x88x921)/2xe2x88x921] (where [ ] is a Gauss symbol, d is a minimum Hamming distance and h is the number of erasures) to calculate the error position polynomial "sgr"(x) and the error evaluator polynomial xcfx89(x), and
a process of calculating an erasure locator polynomial xcex (x) from said erasure locator data xcex1i.
Arithmetic Method
The arithmetic method of this invention calculates the error position polynomial "sgr"(x) and the error evaluator polynomial xcfx89(x) from the updated syndrome polynomial M(x) which is calculated from the erasure locator data xcex1i indicating the locator of an erasure in the linear cyclic code R(x) and the syndrome polynomial S(x) which is calculated from said erasure locator data xcex1i and said linear cyclic code R(x), and repeats recursive formulas;
"sgr"i(x)="sgr"ixe2x88x922(x)+Qi(x)xc2x7"sgr"ixe2x88x921(x)
xcfx89i(x)=xcfx89ixe2x88x922(x)+Qi(x)xc2x7xcfx89ixe2x88x921(x)
where Qi(x) is a quotient of xcfx89ixe2x88x922(x)/xcfx89ixe2x88x921(x), "sgr"xe2x88x92i(x)=1, xcfx89xe2x88x92i(x)=x2t, "sgr"0(x)=1, xcfx890(x)=M(x),
until the degree of the polynomial xcfx89i becomes equal to or less than [(d+hxe2x88x921)/2xe2x88x921] (where [ ] is a Gauss symbol, d is a minimum Hamming distance and h is the number of erasures) to calculate the error position polynomial "sgr"(x) and the error evaluator polynomial xcfx89(x).